package leetcode_1601_1700;

import java.util.Arrays;

public class LeeCode_1621 {
    public static void main(String[] args) {
        System.out.println(numberOfSets(4, 2));
    }
    private static int numberOfSets(int n, int k) {
        long[][][] dp = new long[n][k + 1][2];
        long mod = (long) (1e9 + 7);
        dp[0][0][0] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j <= k; j++) {
                dp[i][j][0] = dp[i - 1][j][0] + dp[i - 1][j][1];
                dp[i][j][0] %= mod;
                dp[i][j][1] = dp[i - 1][j][1];
                dp[i][j][1] %= mod;
                if (j > 0){
                    dp[i][j][1] += dp[i - 1][j - 1][0] + dp[i - 1][j - 1][1];
                    dp[i][j][1] %= mod;
                }
            }
        }
        return (int) ((dp[n - 1][k][0] + dp[n - 1][k][1]) % mod);
    }
}